The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
When data must be stored on a computer that is not trusted, it is often desirable to provide cryptographic authentication of that data using a message authentication code (MAC). For example, when a file server is accessible to a wide group of users, one or more of those users can apply a MAC with a shared secret key to a particular file, and store the MAC tag with the file. The users that also have that same shared secret key then can detect any unauthorized alteration of that file by re-computing the MAC and comparing the re-computed value to a copy of the previously stored MAC tag.
As in any cryptosystem, changing secret keys is sometimes necessary. For example, when multiple users share a secret key, it may be necessary to change a key because one of the users becomes untrusted. If a device containing the key has been stolen or compromised, then a user may no longer be trusted. When a MAC key is changed, the MAC tags for each authenticated data element must be recomputed using the new key. This operation is potentially very costly, because with conventional MAC operations the entire set of authenticated data must be run through a cryptographic function. Using this operation with large data storage systems might require processing gigabytes or terabytes of data using the cryptographic function, which consumes considerable time and processing resources.
An alternative to re-computing the MAC tags is “lazy revocation”, which postpones re-computation of a MAC until a user or other computer requests or fetches the associated data.
Lazy revocation is only useful when it is acceptable to make the assumption that all adversaries seeking to break into the system have limited access to the stored data and MAC tags. A lazy revocation technique is described in “Lazy Revocation in Cryptographic File Systems,” http://www.zurich.ibm.com/4cca/papers/lazyfs.pdf.